def largestRectangleArea(heights):

    stack = [-1] # 用来模拟单调栈

    maxArea = 0 # 结果:最大矩形面积

    for i in range(len(heights)):

        # 当栈不空且当前柱子比栈顶柱子(heights[stack[-1]] )小时
        while len(stack) > 1 and heights[stack[-1]] > heights[i]:

            # 计算以栈顶柱子为高的最大矩形面积
            curHeight = heights[stack.pop()]
            curWidth = i - stack[-1] - 1
            maxArea = max(maxArea, curHeight * curWidth)

        # 将当前柱子索引入栈
        stack.append(i)

    # 遍历结束后,计算余下栈中的柱子形成的矩形面积
    while len(stack) > 1:

        curHeight = heights[stack.pop()]

        # 最后一个矩形,宽度为整个柱状图
        if len(stack) == 1:
            curWidth = len(heights)

        # 其他矩形,宽度为当前柱子索引减去栈顶元素索引
        else:
            curWidth = len(heights) - stack[-1] - 1

        maxArea = max(maxArea, curHeight * curWidth)

    return maxArea

if __name__ == '__main__':

    heights = [2,1,5,6,2,3]
    print(largestRectangleArea(heights))